package solutions;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 
 * @author Luke Valenta
 * @uid lvalenta
 * @id# 112113230
 * @date February 18 - March 12 2014
 * CMSC420 Project 1
 * Stack-less Traversals of Binary Search Trees
 * 
 * This class is an implementation of a Link Inverted Binary Search Tree.
 * Supported operations include insertion, querying for the existence 
 * of an element, pre-order traversal, in-order traversal, post-order traversal,
 * and trivial queries about size, height, and emptiness. Also, pre-order,
 * in-order, and post-order Robson traversals are supported.
 *
 * @param <T> Objects inserted into the tree must be comparable
 */
public class LinkInvertedTree<T extends Comparable<T>> {
	/* Private class variables */
	private Node root; // The root node of the tree
	private int size; // The number of nodes in the tree

	/**
	 * The constructor for the threadedBST
	 * Initialize to a new empty tree with a null root
	 */
	public LinkInvertedTree() {
		root = null;
		size = 0;
	}

	/**
	 * Insert an element into the threaded BST. New nodes are always added at
	 * the leaf level of the tree.
	 * @param element The element to be inserted into the tree
	 */
	public void insert(T element) {
		// Create the node
		Node toInsert = new Node(element);
		
		// Find the correct place in the tree to insert the node
		Node curr = root;
		boolean done = false;
		if(root == null) {
			// Insert the new node at the root
			root = toInsert;
			size = 1;
			done = true;
		}
		while(!done) {
			int comp = toInsert.getData().compareTo(curr.getData());
			if(comp < 0) {
				if(curr.getLeftChild() == null) {
					// Insert the new node here
					curr.setLeftChild(toInsert);
					size++;
					done = true;
				} else {
					// Insert in the left subtree
					curr = curr.getLeftChild();
				}
			} else if (comp > 0) {
				if(curr.getRightChild() == null) {
					// Insert the new node here
					curr.setRightChild(toInsert);
					size++;
					done = true;
				} else {
					// Insert in the right subtree
					curr = curr.getRightChild();
				}
			} else {
				// The element already exists in the tree
				done = true;
			}
		} // end while loop
	}
	
	/**
	 * Extra Credit
	 * 
	 * An iterator that performs a pre-order traversal of the tree's elements
	 * @return An iterator that traverses the tree's elements
	 */
	public Iterator<T> preOrder() {
		ArrayList<T> array = new ArrayList<T>();
		// Perform a pre-order traversal of the tree
		Node p = null, q = root, temp;
		boolean done = false;
		
		while(!done) {
			// Descend as far as possible to the left
			while(q != null) {
				// Visit q (for pre-order)
				array.add(q.getData());
				// Tag(q) <- 0
				q.setTag(false);
				// Descend left
				temp = p;
				p = q;
				q = q.getLeftChild();
				p.setLeftChild(temp);
			}
			// Ascend as far as possible from the right
			while(p != null && p.isTag()) {
				// Ascend from right
				temp = q;
				q = p;
				p = p.getRightChild();
				q.setRightChild(temp);
			}
			// Check exit condition
			if(p == null) {
				done = true;
			} else {
				// Ascend from left
				temp = q;
				q = p;
				p = p.getLeftChild();
				q.setLeftChild(temp);
				// Tag(q) <- 1
				q.setTag(true);
				// Descend right
				temp = p;
				p = q;
				q = q.getRightChild();
				p.setRightChild(temp);
			} // End if
		} // End outer while loop
		return array.iterator();
	}
	
	/**
	 * An iterator that performs an in-order traversal of the tree's elements
	 * @return An iterator that traverses the tree's elements
	 */
	public Iterator<T> inOrder() {
		ArrayList<T> array = new ArrayList<T>();
		// Perform a pre-order traversal of the tree
		Node p = null, q = root, temp;
		boolean done = false;
		
		while(!done) {
			// Descend as far as possible to the left
			while(q != null) {
				// Tag(q) <- 0
				q.setTag(false);
				// Descend left
				temp = p;
				p = q;
				q = q.getLeftChild();
				p.setLeftChild(temp);
			}
			// Ascend as far as possible from the right
			while(p != null && p.isTag()) {
				// Ascend from right
				temp = q;
				q = p;
				p = p.getRightChild();
				q.setRightChild(temp);
			}
			// Check exit condition
			if(p == null) {
				done = true;
			} else {
				// Ascend from left
				temp = q;
				q = p;
				p = p.getLeftChild();
				q.setLeftChild(temp);
				// Visit q (for in-order)
				array.add(q.getData());
				// Tag(q) <- 1
				q.setTag(true);
				// Descend right
				temp = p;
				p = q;
				q = q.getRightChild();
				p.setRightChild(temp);
			} // End if
		} // End outer while loop
		return array.iterator();
	}

	/**
	 * Extra Credit
	 * 
	 * An iterator that performs a post-order traversal of the tree's elements
	 * @return An iterator that traverses the tree's elements
	 */
	public Iterator<T> postOrder() {
		ArrayList<T> array = new ArrayList<T>();
		// Perform a pre-order traversal of the tree
		Node p = null, q = root, temp;
		boolean done = false;
		
		while(!done) {
			// Descend as far as possible to the left
			while(q != null) {
				// Tag(q) <- 0
				q.setTag(false);
				// Descend left
				temp = p;
				p = q;
				q = q.getLeftChild();
				p.setLeftChild(temp);
			}
			// Ascend as far as possible from the right
			while(p != null && p.isTag()) {
				// Ascend from right
				temp = q;
				q = p;
				p = p.getRightChild();
				q.setRightChild(temp);
				// Visit q (for post-order)
				array.add(q.getData());
			}
			// Check exit condition
			if(p == null) {
				done = true;
			} else {
				// Ascend from left
				temp = q;
				q = p;
				p = p.getLeftChild();
				q.setLeftChild(temp);
				// Tag(q) <- 1
				q.setTag(true);
				// Descend right
				temp = p;
				p = q;
				q = q.getRightChild();
				p.setRightChild(temp);
			} // End if
		} // End outer while loop
		return array.iterator();
	}
	
	private class Robson {
		Node top, stack, avail, pres, prev, next;
		ArrayList<T> array;
		int order; // 0 for pre-order, 1 for in-order, 2 for post-order
		
		Robson() {
			pres = root;
			prev = root;
			top = null;
			stack = null;
			avail = null;
			array = new ArrayList<T>();
		}
		
		ArrayList<T> preOrder() {
			order = 0;
			leftmost();
			return array;
		}
		
		ArrayList<T> inOrder() {
			// TODO
			order = 1;
			leftmost();
			return array;
		}
		
		ArrayList<T> postOrder() {
			// TODO
			order = 2;
			leftmost();
			return array;
		}
		
		void leftmost() {
			if(pres.getLeftChild() == null && pres.getRightChild() == null) {
				if(order == 0) {
					// Visit(pres) for all traversals in this case
					array.add(pres.getData());
				}
				avail = pres;
				termination();
			} else if (pres.getLeftChild() != null) {
				if(order == 0) {
					// Visit(pres) for preorder
					array.add(pres.getData());
				}
				// Descend left and then traverse left subtree
				next = pres.getLeftChild();
				pres.setLeftChild(prev);
				prev = pres;
				pres = next;
				leftmost();
			} else { // pres.getRightChild() != null
				if(order == 0) {
					// Visit(pres) for preorder
					array.add(pres.getData());
				}
				// Descend right and then traverse the left subtree
				next = pres.getRightChild();
				pres.setRightChild(prev);
				prev = pres;
				pres = next;
				leftmost();
			}
		}
		
		void termination() {
			// If pres == root, then terminate
			if(pres == root) {
				// Terminate
			} else {
				if(prev.getRightChild() == null) { 
					// Ascend from the left
					next = prev.getLeftChild();
					prev.setLeftChild(pres);
					pres = prev;
					prev = next;
					termination();
				} else if (prev.getLeftChild() == null) {
					// Ascend from the right
					next = prev.getRightChild();
					prev.setRightChild(pres);
					pres = prev;
					prev = next;
					termination();
				} else {
					// If top points to prev, ascend from right. Otherwise, ascend from the left.
					if(prev == top) {
						// Pop stack
						next = stack;
						top = stack.getRightChild();
						stack = stack.getLeftChild();
						// Reset leaf pointers
						next.setLeftChild(null);
						next.setRightChild(null);
						next = prev.getLeftChild();
						prev.setLeftChild(prev.getRightChild());
						prev.setRightChild(pres);
						pres = prev;
						prev = next;
						termination();
					} else {
						// Finished on the left. Push prev onto stack and go right
						avail.setLeftChild(stack);
						avail.setRightChild(top);
						stack = avail;
						top = prev;
						next = prev.getRightChild();
						prev.setRightChild(pres);
						pres = next;
						leftmost();
					}
				}
			}
		}
	}
	
	/**
	 * An iterator that performs a pre-order Robson traversal of the tree's elements
	 * @return An iterator that traverses the tree's elements
	 */
	public Iterator<T> robsonTraversal() {
		return new Robson().preOrder().iterator();
	}
	
	/**
	 * Extra Credit
	 * 
	 * An iterator that performs an in-order Robson traversal of the tree's elements
	 * @return An iterator that traverses the tree's elements
	 */
	public Iterator<T> robsonInorder() {
		return new Robson().inOrder().iterator();
	}
	
	/**
	 * Extra Credit
	 * 
	 * An iterator that performs a post-order Robson traversal of the tree's elements
	 * @return An iterator that traverses the tree's elements
	 */
	public Iterator<T> robsonPostorder() {
		return new Robson().postOrder().iterator();
	}
	
	/**
	 * Returns the height of the tree. A stub tree with only the root
	 * has a height of 1.
	 * @return The height of the tree
	 */
	public int height() {
		// TODO: make sure this is allowed. Otherwise, do iteratively.
		return recursiveHeight(root);
	}
	
	private int recursiveHeight(Node node) {
		if(node == null) {
			return 0;
		} else {
			int left = 0, right = 0;
			if(node.getLeftChild() != null) {
				left = recursiveHeight(node.getLeftChild());
			}
			if(node.getRightChild() != null) {
				right = recursiveHeight(node.getRightChild());
			}
			return 1 + Math.max(left, right);
		}
	}
	
	/**
	 * Find the number of nodes in the tree
	 * @return The number of nodes in the tree
	 */
	public int size() {
		return size;
	}
	
	/**
	 * Determines if the tree contains any elements
	 * @return True if the structure is empty (does not contain 
	 * any elements) and false otherwise
	 */
	public boolean isEmpty() {
		if(size == 0) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * A node for a link-inverted tree, which includes a boolean tag field
	 * that indicates whether or not a link was inverted.
	 */
	private class Node {
		private Node leftChild;
		private Node rightChild;
		private boolean tag;
		private T data;

		Node(T data) {
			this.leftChild = null;
			this.rightChild = null;
			this.data = data;
		}

		Node getLeftChild() {
			return leftChild;
		}

		void setLeftChild(Node leftChild) {
			this.leftChild = leftChild;
		}

		Node getRightChild() {
			return rightChild;
		}

		void setRightChild(Node rightChild) {
			this.rightChild = rightChild;
		}
		
		boolean isTag() {
			return tag;
		}
		
		void setTag(boolean tag) {
			this.tag = tag;
		}

		T getData() {
			return data;
		}

		@SuppressWarnings("unused")
		void setData(T data) {
			this.data = data;
		}
	} // End of Node class
}
